package _03_栈;

import java.util.Arrays;
import java.util.Stack;

public class _739_每日温度 {

    public static void main(String[] args) {
        int[] is = {73, 74, 75, 71, 69, 72, 76, 73};
        _739_每日温度 v = new _739_每日温度();
        int[] ints = v.dailyTemperatures(is);
        System.out.println(Arrays.toString(ints));
    }

    public int[] dailyTemperatures(int[] temperatures) {
        int[] values = new int[temperatures.length];
        for (int i = temperatures.length - 2; i >= 0; i--) {
            int j = i + 1;
            while (true) {
                if (temperatures[i] < temperatures[j]) {
                    values[i] = j - i;
                    break;
                } else if (values[j] == 0) {
                    values[i] = 0;
                    break;
                }
                j = j + values[j];
            }
        }

        return values;
    }

    // 递推法
    public int[] dailyTemperatures2(int[] temperatures) {
        int[] values = new int[temperatures.length];
        for (int i = temperatures.length - 2; i >= 0; i--) {
            int j = i + 1;
            while (true) {
                if (temperatures[i] < temperatures[j]) {
                    values[i] = j - i;
                    break;
                } else if (temperatures[i] == temperatures[j]) {
                    if (values[j] == 0) {
                        values[i] = 0;
                    } else {
                        values[i] = values[j] + j - i;
                    }
                    break;
                } else {
                    if (values[j] == 0) {
                        values[i] = 0;
                        break;
                    } else {
                        j = j + values[j];
                    }
                }
            }
        }

        return values;
    }

    // 栈实现
    public int[] dailyTemperatures1(int[] temperatures) {
        int[] nums = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                nums[stack.pop()] = i;
            }
            stack.push(i);
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] == 0 ? 0 : nums[i] - i;
        }
        return nums;
    }

}
